For improving the processing performance of arithmetic processing apparatuses such as CPUs (Central Processing Unit), etc., there have been known techniques by which a next instruction is speculatively executed without waiting for the current instruction to be executed. However, in the case of branch instructions, a branch instruction needs to be finished before a next instruction starts because the address of the next instruction is determined by executing the branch instruction. To deal with this, branch prediction techniques have widely been used, which predict the address of a next instruction, so as to start the execution of the next instruction before the branch instruction is executed.
One of the known branch prediction techniques uses information indicating a history of past branches called a branch history or global history in order to predict a branch target. Further, to improve the accuracy of branch prediction for a return instruction to return from a subroutine, there has been known a technique of pushing a return destination address for a return instruction on a return address stack when executing a call instruction to call the subroutine, and then popping the branch target as a prediction from the return address stack when executing the return instruction. Still further, for using a general-purpose register to generate branch target addresses of branch instructions, there has also been a branch prediction technique of managing changes in the contents of the general-purpose register used to generate branch target addresses, and determining based on the changes whether a result of a branch prediction based on a branch history is correct or not.
As another reference technique, there has been a program development support apparatus for debugging, which obtains a plurality of branch target addresses corresponding to a branch instruction and the frequency of each branch target through simulation, registers them in a table, and predicts the address of a next instruction with reference to this table.
Japanese Laid-open Patent Publication No. 2006-155374
Japanese Laid-open Patent Publication No. 4-225429
Japanese Laid-open Patent Publication No. 2001-184231
Out of branch instructions, instructions such as conditional branches, unconditional branches, subroutine calls, etc. each have a fixed branch target instruction address. On the other hand, like instructions represented as switch/case statements in C language, there are instructions that each have a plurality of branch targets according to conditions. In executing a branch instruction having a plurality of branch targets, it is difficult to predict a branch target because, even if it is predictable whether a branch will be taken or not-taken, the address of the branch target instruction is determined by executing the previous instruction.